﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace schedule
{
    class TaskParams
    {
        public int i;
        public TaskThread tt;

        public TaskParams(int index)
        {
            i = index;
            tt = null;
        }
    }

    class TaskThread
    {
        TaskDistributor distributor;
        int threadID;
        IDEQueue<TaskParams> localTaskQueue;
        public TaskDistributor.taskOp taskOp;

        public TaskDistributor Distributor
        {
            set { distributor = value; }
        }
        public int ID
        {
            get { return threadID; }
            set { threadID = value; }
        }
        public IDEQueue<TaskParams> LocalTaskQueue
        {
            get { return localTaskQueue; }
        }
        public int TaskNum
        {
            get
            {
                UnboundedDEQueue<TaskParams> udeq = localTaskQueue as UnboundedDEQueue<TaskParams>;
                return udeq.bottom - udeq.top;
            }
        }

        /// <summary>
        /// ctors
        /// </summary>
        /// <param name="op"></param>
        public TaskThread(TaskDistributor td, TaskDistributor.taskOp op, int id)
        {
            taskOp = op;
            distributor = td;
            threadID = id;
            localTaskQueue = new UnboundedDEQueue<TaskParams>();
        }
        public TaskThread(TaskDistributor.taskOp op)
        {
            taskOp = op;
            localTaskQueue = new UnboundedDEQueue<TaskParams>();
        }
        public TaskThread()
        {
            taskOp = null;
            localTaskQueue = new UnboundedDEQueue<TaskParams>();
        }


        public void run()
        {
            //taskOp.BeginInvoke(localTaskQueue.popBottom(), this.taskThreadComplete, null);
            Thread thread = new Thread(new ThreadStart(defaultTaskOp));
            thread.Start();
        }

        public void taskThreadComplete()
        {
            distributor.setTaskFlag(ID, false);
            System.Console.WriteLine("Thread {0} with signature {1} finished, and set the flag to false\n", 
                Thread.CurrentThread.GetHashCode(), ID);
        }

        public void defaultTaskOp()
        {
            while (!localTaskQueue.isEmpty())
            {
                TaskParams tp = localTaskQueue.popBottom();
                int id = Thread.CurrentThread.GetHashCode();
                System.Console.WriteLine("Thread {0} with signature {2} is working on item {1}", id, tp.i, ID);
                Random r = new Random();
                int duration = r.Next(200, 350);
                if (tp.tt.ID == 0)
                    duration = r.Next(100, 250);
                Thread.Sleep(duration);

                System.Console.WriteLine("Thread {0} with signature {2} finished processing on item {3} with {1} ms", id, duration, ID, tp.i);
            }
            this.taskThreadComplete();
        }

    }

    class TaskDistributor
    {
        public delegate void taskOp();

        Queue<TaskParams> taskQueue;
        bool[] taskFlags;
        TaskThread[] threadPool;

        int loopCount = 0;


        public void setTaskFlag(int index, bool flag)
        {
            taskFlags[index] = flag;
        }

        int getIdleThread()
        {
            for (int i = 0; i < taskFlags.Length; ++i)
            {
                if (taskFlags[i] == false)
                    return i;
            }

            return -1;
        }

        public TaskDistributor(int numThreads)
        {
            taskQueue = new Queue<TaskParams>();

            taskFlags = new bool[numThreads];
            threadPool = new TaskThread[numThreads];

            for (int i = 0; i < numThreads; ++i)
            {
                threadPool[i] = new TaskThread(this, null, i);
                threadPool[i].taskOp = threadPool[i].defaultTaskOp;
            }

        }

        public void addTask(TaskParams task)
        {
            taskQueue.Enqueue(task);
        }

        /// <summary>
        /// Distribute the tasks buffered in taskQueue
        /// </summary>
        public void updata()
        {
            ++loopCount;
            int idleThreadIndex;
            while ((idleThreadIndex = this.getIdleThread()) != -1)
            {
                // always consider fill the thread local taskQueue with the task
                // in the distributor's task queue first
                if (taskQueue.Count > 0)
                {
                    while (taskQueue.Count > 0)
                    {
                        TaskParams tp = taskQueue.Dequeue();
                        tp.tt = threadPool[idleThreadIndex];
                        threadPool[idleThreadIndex].LocalTaskQueue.pushBottom(tp);

                        System.Console.WriteLine("assign work to thread {0} from task queue at loop {1}", idleThreadIndex, loopCount);
                    }
                    taskFlags[idleThreadIndex] = true;
                    threadPool[idleThreadIndex].run();

                    return;
                }
                //if (taskQueue.Count > 0)
                //{
                //    TaskParams tp = taskQueue.Dequeue();
                //    tp.tt = threadPool[idleThreadIndex];
                //    threadPool[idleThreadIndex].LocalTaskQueue.pushBottom(tp);
                //    taskFlags[idleThreadIndex] = true;  System.Console.WriteLine("assign work to thread {0} from task queue at loop {1}", idleThreadIndex, loopCount);
                //    threadPool[idleThreadIndex].run(); 
                //    continue;
                //}

                // if distributor's task queue is empty,
                // we steal task from other threads
                int maxTaskIndex = 0;
                foreach (TaskThread tt in threadPool)
                {
                    if (tt.TaskNum > threadPool[maxTaskIndex].TaskNum)
                        maxTaskIndex = tt.ID;
                }
                if (threadPool[maxTaskIndex].TaskNum == 0)
                    return;

                TaskParams taskParam = threadPool[maxTaskIndex].LocalTaskQueue.popTop();
                taskParam.tt = threadPool[idleThreadIndex];
                threadPool[idleThreadIndex].LocalTaskQueue.pushBottom(taskParam);
                taskFlags[idleThreadIndex] = true;   System.Console.WriteLine("steal work to thread {0} from thread {1} at loop {2}", idleThreadIndex, maxTaskIndex, loopCount);
                threadPool[idleThreadIndex].run();
               
            }
        }

        public bool finished
        {
            get
            {
                foreach (bool b in taskFlags)
                    if (b)
                        return false;

                return taskQueue.Count == 0;
            }
        }

    }
}
